#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "pagina.h"

int main(int argc, char *argv[]) {
   /* ----------------------------------------------------------------------
      Declaracoes e inicio para verificacao do uso da memoria dinamica.
      ---------------------------------------------------------------------- */
   struct mallinfo info = mallinfo();
   int MemDinInicial = info.uordblks, MemDinFinal;
   /* ---------------------------------------------------------------------- */

	int i, j, tamanhoLista, vizinho, nVizinhos;
	ListaCorresponde *listaCorresponde = NULL;
	Grafo *lista;
	char site[500],comando[500],origem[500],destino[500];
	int or,des,igual;
	
	scanf(" %d", &tamanhoLista);
	
	if(!tamanhoLista) return 0; 
	
	lista = (Grafo *)MontaGrafo(tamanhoLista);
	
	for(i=0; i<tamanhoLista; i++)
	{
		scanf("%s", site);
		insereCorresponde(&listaCorresponde, site, i); /* insere na listaCorresponde para depois acessar os indices dos sites passados */
		
		scanf(" %d", &nVizinhos);
		
		for(j=0; j<nVizinhos; j++)
		{
			scanf(" %d", &vizinho);
			insereVizinho(&lista->vetor[i].viz, vizinho);
		}
	}

	while(strcmp(comando,"sair") != 0)
	{
		for (i = 0;i < tamanhoLista;i++)
			lista->vetor[i].caminhomin = LONG_MAX;
		scanf("%s",comando);
		if (strcmp(comando,"sair") == 0)
			break;
		scanf("%s",origem);		
		scanf("%s",destino);
		
		or = corresponde(&listaCorresponde,origem);
		des = corresponde(&listaCorresponde,destino);
		
		igual = checaIgual(or,des);

		dijkstra(lista,or,tamanhoLista);
		
		if (lista->vetor[des].caminhomin < LONG_MAX && !igual)
			printf("Menor caminho entre %s e %s: %d link(s)\n",origem,destino,lista->vetor[des].caminhomin);
		else
			printf("N\xe3o existe caminho de %s para %s\n",origem,destino);
	}

	liberaListaP(&lista,tamanhoLista);
	liberaListaC(&listaCorresponde);

   /* --------------------------------------------------------------------- */
   /* Verificacao final do uso da memoria dinamica                          */
   /* --------------------------------------------------------------------- */
   info = mallinfo();
   MemDinFinal = info.uordblks;
   if (MemDinInicial!=MemDinFinal)
      printf("\n\nMemoria dinamica nao foi totalmente liberada (%d, %d)\n",
	     MemDinInicial,MemDinFinal);
   /* --------------------------------------------------------------------- */
   return 0;
}
